package com.gcloud.mesh.heuristicAlgorithm;

import java.security.SecureRandom;
import java.util.Collection;
import java.util.HashMap;
import java.util.concurrent.ConcurrentHashMap;

import com.gcloud.mesh.distributedSchedule.ICluster;
import com.gcloud.mesh.distributedSchedule.IEvaluateFactor;
import com.gcloud.mesh.distributedSchedule.application.Application;

import lombok.extern.slf4j.Slf4j;

/**
 * 遗传算法实现
 */
@Slf4j
public class geneticAlgorithm {

    // TODO: 并发度
    private int concurrentLevel = 1;

    private int populationAmount;

    private String[] geneCodeList;

    private String[][] population;

    private int geneLinkLength;

    // 记录每次迭代每个样本的评估结果
    private HashMap<String, IEvaluateFactor.evalResult>[] evalScore = null;

    private int maxCalTime;
    
    private SecureRandom rd = new SecureRandom();

    /**
     * @param geneLinkLength  基因链长度 (要调度的应用的数量）
     * @param availGeneCode   基因可以使用的表达编码的列表，顺序无关
     * @param concurrentLevel 并发度，大于等于1小于等于10，控制计算时的速度
     * @param maxCalTime       最多迭代次数，如果超出此数则不论结果如何都会终止，建议不小于 geneLinkLength * availGeneCode.length
     */
    public geneticAlgorithm(int geneLinkLength, String[] availGeneCode, int concurrentLevel, int maxCalTime) {
        this.geneLinkLength = geneLinkLength;
        this.maxCalTime = maxCalTime;

        // TODO: 3倍是否足够容易足够的基因差异性？
        this.populationAmount = availGeneCode.length * 3;
        this.concurrentLevel = concurrentLevel;
        this.geneCodeList = availGeneCode;

        // generate init sample.
        int len = availGeneCode.length;
        this.population = new String[this.populationAmount][geneLinkLength];
        for (int i = 0; i < this.populationAmount; i++) {
            for (int j = 0; j < geneLinkLength; j++) {
                // randomly choose a gene code.
                this.population[i][j] = this.geneCodeList[(int)(rd.nextDouble() * 10 * len) % len];
            }
        }
    }

    public String[] evaluate(IEvaluateFactor[] evaluators, Application[] apps, ConcurrentHashMap<String, ICluster> clusters) throws Exception {
        int[] selected = null;
        int count = 0;
        HashMap<String, IEvaluateFactor> evMap = new HashMap<>();

        boolean highest = false;
        for (IEvaluateFactor ef : evaluators) {
            if (ef.getLevel() == IEvaluateFactor.Level.HIGH) {
                if (highest == true) {
                    log.error("设置为最高权重的评价函数多于一个，错误！");
                    throw new Exception("设置为最高权重的评价函数多于一个");
                }
                else
                    highest = true;
            }
        }

        for (IEvaluateFactor ev : evaluators) {
            evMap.put(ev.getId(), ev);
        }

        while (true) {
            this.evalScore = new HashMap[this.populationAmount];

            for (int i = 0; i < this.populationAmount; i++) {
                this.evalScore[i] = new HashMap<String, IEvaluateFactor.evalResult>();

                // TODO: multi-threads optimization.
                for (IEvaluateFactor ef : evaluators) {
                    IEvaluateFactor.evalResult er = ef.evaluate(apps, clusters, this.population[i]);
                    this.evalScore[i].put(ef.getId(), er);
                }
            }
            // 归一化数据，否则不同维度（评价函数）的分数范围差异过大，比较统计和毫无意义。
            // 第一次先在所有样本上对同类评价函数的分数求和求平均，得到该评价函数的大致得分范围，
            // 然后对比不同维度的平均分的大小差异，求出不同维度的缩放系数。
            // 以后 维度得分 * 缩放系数 * 等级权重系数 = 最终拿来比较的分数
            if (evaluators[0].scaleFactorInit() == false) {
                this.scaleFactorCalculate(this.evalScore, evaluators);
            }

            // 排序，cmp, 挑出优秀样本
            selected = this.select(this.evalScore, evMap);

            // 在更新population之前，判断是否符合退出条件
            if (this.stop(selected, count++)) break;

            // 基因进化,更新样本
            this.population = this.evolute(selected);

            log.debug("calculating time: " + count);
        }

        return this.population[selected[0]];
    }

    /**
     * 求缩放系数
     */
    private void scaleFactorCalculate(HashMap<String, IEvaluateFactor.evalResult>[] evalScore, IEvaluateFactor[] evaluators) {
        HashMap<String, IEvaluateFactor.evalResult> index = evalScore[0];
        HashMap<String, Double> scores = new HashMap<>();

        for (String evId : index.keySet()) {
            double sum = 0;
            for (int i = 0; i < evalScore.length; i++) {
                sum += evalScore[i].get(evId).score;
            }
            scores.put(evId, sum / evalScore.length);
        }

        // 统计了各个评价函数分数的平均分后，开始计算缩放系数
        double max = 0;
        for (String evId : scores.keySet()) {
            if (scores.get(evId) > max) {
                max = scores.get(evId);
            }
        }

        //       evId    scaleFactor
        HashMap<String, Double> scaleFactor = new HashMap<>();
        for (String evId : scores.keySet()) {
            scaleFactor.put(evId, max / scores.get(evId));
        }

        for (IEvaluateFactor ev : evaluators) {
            ev.setScaleFactor(scaleFactor.get(ev.getId()));
        }
    }

    /**
     * 停止迭代判断,硬性条件是有样本的所有评估函数结果都为真
     */
    private boolean stop(int[] selected, int count) {
        if (this.evalScore != null && selected != null) {
            return false;
        }
        if (count > this.maxCalTime) {
            log.warn("exceed the maximum allowed calculating times.");
            return true;
        }
        // selected[0] is the highest score.
        Collection<IEvaluateFactor.evalResult> vals = this.evalScore[selected[0]].values();
        for (IEvaluateFactor.evalResult v : vals) {
            if (v.qualified == false)
                return false;
        }

        return true;
    }

    private class LinkList {
        public int index = 0;
        public int score = 0;
        public LinkList next;

        public LinkList(int index, int score) {
            this.index = index;
            this.score = score;
            this.next = null;
        }
    }

    /**
     * 选择函数，选择哪些样本作为父辈,没有被选择的则淘汰,选择多少个呢？
     * TODO: 把选择算子抽象出public接口
     */
    private int[] select(HashMap<String, IEvaluateFactor.evalResult>[] evalScore, HashMap<String, IEvaluateFactor> evMap) {
        int[] totalScore = new int[evalScore.length];

        // TODO: 选择多少个呢？太多降低收敛速度，太少损失潜在的优秀基因片段
        int[] selectList = new int[evalScore.length / 2];

        // TODO: 改进此处
        // 原则上来说，只有所有评价函数都合格了样本才算合格，但是在迭代的初期，可能根本没有
        // 样本是都符合评价函数的，根本无法选优。因此只能通过评价函数给样本打一个分数，通过
        // 分数的高低来选优。而在迭代后期，样本应该有都符合各个评价函数的，这个时候就选用这些
        // 评价函数都合格的样本.资料中这种选择策略叫“均匀排序”，基于评分大小的选择策略，是
        // 因为我们的使用场景中评价函数方便打分，具有特殊性.
        for (int i = 0; i < evalScore.length; i++) {

            int scoreSum = 0;

            // 把各个评价函数打的分叠加起来，分数高就用哪个
            for (IEvaluateFactor.evalResult er : evalScore[i].values()) {
                // 累加修正得分
                scoreSum += evMap.get(er.evaluatorId).getFixedScore(er.score);
            }
            // TODO: 现在是通过简单累加各个评价函数的得分，而事实上各个评价函数的分数是不同维度的，
            // 因此直接累加不是十分合适，不过却是最简单的方案，有待改进，可以对各个评价函数在不同的
            // 样本分数上进行归一化操作，把最高分那个归一化为100，其他按比例归一化,归一化了再累加
            totalScore[i] = scoreSum;
        }

        // descending sort depend on scores.
        LinkList head = new LinkList(0, 0);
        for (int i = 0; i < totalScore.length; i++) {
            LinkList insert = head;
            if (totalScore[i] > head.score) {
                head = new LinkList(i, totalScore[i]);
                head.next = insert;
            }
            else {
                while (insert != null) {
                    if (totalScore[i] < insert.score) {
                        if (insert.next == null) {
                            LinkList node = new LinkList(i, totalScore[i]);
                            insert.next = node;
                            break;
                        }
                        else if (totalScore[i] > insert.next.score) {
                            LinkList node = new LinkList(i, totalScore[i]);
                            node.next = insert.next;
                            insert.next = node;
                            break;
                        }
                        else {
                            insert = insert.next;
                        }
                    }
                }
            }
        }

        // pick out the index of highest scores.
        LinkList node = head;
        for (int i = 0; i < selectList.length; i++) {
            selectList[i] = node.index;
            node = node.next;
        }

        return selectList;
    }

    /**
     * 更新基因片段,生成新的样本。
     * 优选出的样本是总样本数量的一半，要生成和初始样本一样数量的样本
     */
    private String[][] evolute(int[] selected) {
        String[][] newPopulation = new String[this.populationAmount][this.geneLinkLength];
        int selectedLength = selected.length;
        int populate = 0;

        // the first two samples have highest score, so diffuse their gene code
        // to new samples as more as possible.
        for (int father = 0; father < 2; father++) {
            for (int mother = father+1; mother < selectedLength; mother++) {
                String[] son = this.crossover(this.population[selected[father]], this.population[selected[mother]]);
                newPopulation[populate++] = son;
            }
        }
        // 还剩下3个空位，放入上一批样本中分数最高的三个。
        // 我也不十分肯定这样做有好处，不过对于防止种群适应性退化应该是有好处的
        newPopulation[populate] = this.population[selected[0]];
        newPopulation[populate+1] = this.population[selected[1]];
        newPopulation[populate+2] = this.population[selected[2]];

        return newPopulation;
    }

    // 交换基因片段，生成一个后代
    // TODO: 有没有更好的交换策略
    private String[] crossover(String[] father, String[] mother) {

        // 引入策略随机性，优良基因可能分布在左边或右边
        int rnd = rd.nextDouble() > 0.5 ? 0 : 1;
        String[] son = new String[father.length];

        for (int i = 0; i < father.length; i++) {
            if (i % 2 == rnd)
                son[i] = father[i];
            else
                son[i] = mother[i];
        }

        return son;
    }

    /**
     * 变异
     * @param origSample
     * @return
     */
    private String[] mutate(String[] origSample) {
        return null;
    }
}
